package com.hainiu.cat.sort;

import static com.hainiu.cat.sort.FastSort.arrayToString;

/**
 * create by biji.zhao on 2021/5/28
 *
 * =========================堆排序法================================
 *
 * 删除元素：（最大堆）
 *  删除堆顶元素，
 *      1、将数组最后一个元素和第一个元素交换，交换完成，删除数组最后一个元素。
 *      2、让堆顶元素和两个子节点元素比较，比之最大大则退出，否则下沉，和最大的子节点元素交换
 *
 *
 *      以下为堆中数组所对应的下标
 *                  0
 *       1       2        3      4
 *     5  6    7  8     9  10  11 12
 *
 * @link {https://developer.51cto.com/art/202003/612043.html}  优化的堆排序
 */
public class DuiSort {

    private int[] data;

    /**
     * 向堆添加一个元素
     * @param e 元素
     */
    public void add(int e) {
        data = addToArray(data, e);
        siftUp(data, data.length - 1);
    }

    /**
     * 向数组添加一个元素
     * @param data 数组
     * @param e  元素
     * @return 新元素
     */
    private static int[] addToArray(int[] data, int e) {
        int[] target = new int[data.length + 1];
        System.arraycopy(data, 0, target, 0, data.length);
        target[data.length] = e;
        return target;
    }

    /**
     * 移除数组中最后一个元素，这里使用数组的copy
     * @param data 数组
     * @return     移除后的新数组
     */
    private static int[] removeLast(int[] data) {
        if (data.length == 0 || data.length == 1) {
            return new int[0];
        }
        int[] target = new int[data.length - 1];
        System.arraycopy(data, 0,  target, 0, data.length - 1);
        return target;
    }

    /**
     * 上浮
     * @param data  数组
     * @param k     节点位置
     */
    private static void siftUp(int[] data, int k) {
        while (k > 0 && data[k] > data[getParent(k)]) {
            swap(data, k, getParent(k));
            k = getParent(k);
        }
    }

    /**
     * 下沉
     * @param data  数组
     * @param k     节点位置
     */
    private static void shiftDown(int[] data, int k) {
        // 完全二叉树，如果没有左节点则退出
        while (getLeftChild(k) < data.length) {
            // 先获取左节点
            int j = getLeftChild(k);
            // 判断右节点是否比左节点大，如果是，则将右节点位置赋值给j
            if (j + 1 < data.length && data[j + 1] > data[j]) {
                j = getRightChild(k);
            }
            // 如果父节点大，则退出
            if (data[k] >= data[j]) {
                break;
            }
            // 如果子节点最大值更大，则交换
            swap(data, k, j);
            // 将指针指向大子节点，继续循环下去
            k = j;
        }
    }

    /**
     * @return 得到堆顶的元素
     */
    private int extractMax() {
        int max = data[0];
        swap(data, 0, data.length - 1);
        data = removeLast(data);
        shiftDown(data, 0);
        return max;
    }

    /**
     * 交换数组中两个小标位置的元素
     */
    private static void swap(int[] data, int o, int t) {
        int temp = data[o];
        data[o] = data[t];
        data[t] = temp;
    }

    public static void main(String[] args) {
        int[] sort = {1, 3, 56, 7, 9, 2};

        DuiSort duiSort = new DuiSort();
        duiSort.data = new int[0];
        for (int i = 0; i < sort.length; i++) {
            duiSort.add(sort[i]);
        }
        for (int i = sort.length - 1; i >= 0; i--) {
            sort[i] = duiSort.extractMax();
        }
        System.out.println(arrayToString(sort));
    }

    /**
     * 得到父节点所在数组位置
     */
    private static Integer getParent(int i) {
        return (i - 1) / 2;
    }

    /**
     * 得到左子节点所在数组位置
     */
    private static Integer getLeftChild(int i){
        return i * 2  + 1;
    }

    /**
     * 得到右子节点所在数组位置
     */
    private static Integer getRightChild(int i) {
        return i * 2 + 2;
    }
}
